package solution._0030._0035;

/**
 * Created by chen_snow
 * Date: 2021/6/1 23:16
 * Description:
 */
public class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0 || nums[0] > target) {
            return 0;
        }

        if (nums[nums.length - 1] < target) {
            return nums.length;
        }

        return halfSearch(nums, target, 0, nums.length - 1);
    }

    public int halfSearch(int[] nums, int target, int start, int end) {
        if (start >= end) {
            return nums[start] < target ? start + 1 : start;
        }

        int middle = start + (end - start) / 2;

        if (nums[middle] == target) {
            return middle;
        }

        if (nums[middle] > target) {
            return halfSearch(nums, target, start, middle - 1);
        } else {
            return halfSearch(nums, target, middle + 1, end);
        }
    }
}
